package gold.gold02;

/**
 * 树, 递归
 */
public class S0410检查子树 {
    /**
     * 96, 找到节点值相同的节点之后, 查看这个节点的子树是不是和t2一模一样
     */
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if(t1 == null && t2 == null) return true;
        if(t1 == null || t2 == null) return false;
        if(t1.val == t2.val && equalTree(t1, t2)){
            return true;
        }else{
            return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
        }
    }
    // 判断两个树是否完全相同
    public boolean equalTree(TreeNode t1, TreeNode t2){
        if(t1 == null && t2 == null) return true;
        if(t1 == null || t2 == null) return false;
        if(t1.val == t2.val){
            return equalTree(t1.left, t2.left) && equalTree(t1.right, t2.right);
        }else{
            return false;
        }
    }

    /**
     * 这个和我一模一样
     */
    public boolean checkSubTree2(TreeNode t1, TreeNode t2) {
        if(t1==null){
            return false;
        }
        if(t2==null){
            return false;
        }
        return dfs(t1,t2) || checkSubTree(t1.right,t2) || checkSubTree(t1.left,t2);
    }
    public boolean dfs(TreeNode t1, TreeNode t2){
        if(t2==null){
            return true;
        }
        if(t1==null){
            return false;
        }
        if(t1.val!=t2.val){
            return false;
        }
        return dfs(t1.left,t2.left) && dfs(t1.right,t2.right);
    }
}
